\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  \(N\) 是 \(5e3\) 级别，可以区间 \(dp\)：\(O(N^2)\)\\
  \(f[i][j] = max(f[i][j] , f[i+1][j],f[i][j - 1])\)
\item
  \(N\) 是 \(5e4\) 级别，考虑分块：\\
  记 \(b_{l,r}\) 表示第 \(l\) 块到第 \(r\) 块之间的答案\\
  这个可以用 \(trie\) \(O(n\sqrt{n}\log S)\) 搞出来，\(S\) 是值域
\end{itemize}

\begin{lstlisting}
#define Int int
#define MAXN 100005
#define num bel[n]

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,cur,rt[MAXN],val[MAXN],bel[MAXN];
int ch[MAXN * 32][2],cnt[MAXN * 32],Ans[705][705];

int sta[705],fin[705];

void Insert (int a,int b,int t,int x){
	if (t < 0) return ;
	int i = (x >> t) & 1;
	ch[a][i] = ++ cur;
	ch[a][i ^ 1] = ch[b][i ^ 1];
	cnt[ch[a][i]] = cnt[ch[b][i]] + 1;
	Insert (ch[a][i],ch[b][i],t - 1,x);
}

int query (int a,int b,int t,int x){
	if (t < 0) return 0;
	int i = (x >> t) & 1;
	if (cnt[ch[a][i ^ 1]] > cnt[ch[b][i ^ 1]]) return (1 << t) + query (ch[a][i ^ 1],ch[b][i ^ 1],t - 1,x);
	else return query (ch[a][i],ch[b][i],t - 1,x);
}

signed main(){
	read (n,m);
	int siz = sqrt (n);
	memset (sta,0x7f,sizeof (sta));
	for (Int i = 1;i <= n;++ i) read (val[i]),bel[i] = (i - 1) / siz + 1;
	for (Int i = 1;i <= n;++ i) sta[bel[i]] = min (sta[bel[i]],i),fin[bel[i]] = i;
	for (Int i = 1;i <= n;++ i) rt[i] = ++ cur,Insert (rt[i],rt[i - 1],17,val[i]);
	for (Int i = 1;i <= num;++ i){
		int start = sta[i];
		for (Int j = i;j <= num;++ j){
			Ans[i][j] = Ans[i][j - 1];
			for (Int k = sta[j];k <= fin[j];++ k)
				Ans[i][j] = max (Ans[i][j],query (rt[k],rt[start - 1],17,val[k]));
		}
	}
	while (m --){
		int l,r;
		read (l,r);
		if (bel[r] - bel[l] <= 2){
			int ans = 0;
			for (Int i = l;i < r;++ i)
				ans = max (ans,query (rt[r],rt[i],17,val[i]));
			write (ans),putchar ('\n');
		}
		else{
			int bl = bel[l] + 1,br = bel[r] - 1;
			int ans = Ans[bl][br];
			for (Int i = l;i < sta[bl];++ i) ans = max (ans,query (rt[r],rt[l - 1],17,val[i]));
			for (Int i = fin[br] + 1;i <= r;++ i) ans = max (ans,query (rt[i],rt[l - 1],17,val[i]));
			write (ans),putchar ('\n');
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
